#include "Sort.h"
void Swap(int *a,int *b)
{
    int p=*a;
    *a=*b;
    *b=p;
}

void BubbieSort(int *a,int len,int (*s)(int a,int b))
{
    for(int i=1;i<len;i++)
    {
        int flag=0;
        for(int j=0;j<len-i;j++)
        {
            if(s(a[j],a[j+1]))
            {
                int temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;
                flag=1;
            }
        }
        if(flag==0)
            break;
    }
}

void InsertSort(int *a,int len)
{
    for(int i=0;i<len;i++)
    {
        int temp=a[i];
        int j=i; 
        for(;j>0;j--)
        {
            if(a[j-1]>temp)
                a[j]=a[j-1];
            else
                break;
        }
        a[j]=temp;
    }
}

void ChooseSort(int *a,int len)
{
    for(int i=0;i<len;i++)
    {
        int min=i;
        for(int j=i;j<len;j++)
        {
            if(a[j]<a[min])

                min=j;
        }
        int temp=a[i];
        a[i]=a[min];
        a[min]=temp;
    }
}

void ChooseSort2(int *a,int len)
{
    int left=0;
    int right=len-1;
    while(left<right)
    {
        int min=left;
        int max=right;
        for(int i=left;i<=right;i++)
        {
            if(a[i]<a[min])
                min=i;
            if(a[i]>a[max])
                max=i;
        }
        swap(&a[left],&a[min]);
        if(max==left)
        {
            max=min;
        }
        swap(&a[right],&a[max]);
        left++;
        right--;

    }
}

void FastSort(int *a,int start,int end)
{
    int left=start;
    int right=end;
    int temp=a[start];
    while(left<right)
    {
        while(a[right]>temp&&left<right)
        {
            right--;
        }
        if(left<right)
        {
            a[left]=a[right];
            left++;
        }
        while(left<right&&a[left]<temp)
        {
            left++;
        }
        if(left<right)
        {
        a[right]=a[left];
        right--;
        }
        a[left]=temp;
        
        fastsort(a,start,left-1);
        fastsort(a,right+1,end);
    }
}
